package com.zx._12_算法.数据结构.array;

import java.util.Arrays;

public class ArrayDemo {

    // 有序数组去重
    // 我们知道对于数组来说，在尾部插入、删除元素是比较高效的，时间复杂度是 O(1)，但是如果在中间或者开头插入、删除元素，就会涉及数据的搬移，时间复杂度为 O(N)，效率较低。
    // 所以对于一般处理数组的算法问题，我们要尽可能只对数组尾部的元素进行操作，以避免额外的时间复杂度。
	/* 解题思路：包括链表，也可以按照这样的思路实现
		对于数组相关的算法问题，有一个通用的技巧：要尽量避免在中间删除元素，那我就先想办法把这个元素换到最后去。
		这样的话，最终待删除的元素都拖在数组尾部，一个一个 pop 掉就行了，每次操作的时间复杂度也就降低到 O(1) 了。
		按照这个思路呢，又可以衍生出解决类似需求的通用方式：双指针技巧。具体一点说，应该是快慢指针。
		我们让慢指针slow走左后面，快指针fast走在前面探路，找到一个不重复的元素就告诉slow并让slow前进一步。
		这样当fast指针遍历完整个数组nums后，nums[0..slow]就是不重复元素，之后的所有元素都是重复元素。
	*/
    public static void main(String[] args) {
        removeDuplicates(new int[]{1, 2, 3});
        removeDuplicates(new int[]{1, 1, 2});
        removeDuplicates(new int[]{0, 0, 1, 1, 1, 2, 2, 3, 3, 4});
    }

    public static void removeDuplicates(int[] nums) {
        int len = nums.length;
        int fast = 1;// 指针位置
        int slow = 0;// 指针位置

        while (fast < len) {
            if (nums[fast] == nums[slow]) {//发现是一个的值，fast就往下走
                fast++;
            } else {
                nums[slow + 1] = nums[fast];
                fast++;
                slow++;
            }
        }
        System.out.println(slow + 1 + "=" + Arrays.toString(nums));
    }

}
 